package antonst.list;

import java.util.EmptyStackException;
import java.util.Iterator;

public class MyLinkedList<E> implements MyList<E>, MyQueue<E>, MyStack<E> {

	private Node<E> head;
	private Node<E> tail;

	private int size = 0;

	public MyLinkedList() {

	}

	public MyLinkedList(MyList<E> c) {
		for (E element : c) {
			this.add(element);
		}
		size = c.size();
	}

	public void addFirst(E e) {
		Node<E> nodeToInsert = new Node<E>(e);
		addNodes(head, nodeToInsert, nodeToInsert, 1);
	}

	public void addLast(E e) {
		Node<E> nodeToInsert = new Node<E>(e);
		addNodes(null, nodeToInsert, nodeToInsert, 1);
	}

	public E getFirst() {
		return head.element;
	}

	public E getLast() {
		return tail.element;
	}

	public E removeFirst() {
		Node<E> nodeToRemove = head;
		removeNode(nodeToRemove);
		return nodeToRemove.element;
	}

	public E removeLast() {
		Node<E> nodeToRemove = tail;
		removeNode(nodeToRemove);
		return nodeToRemove.element;
	}

	public Iterator<E> descendingIterator() {
		Iterator<E> iteratorToReturn = new MyDescendingIterator(tail);
		return iteratorToReturn;
	}

	@Override
	public Iterator<E> iterator() {
		Iterator<E> iteratorToReturn = new MyIterator(head);
		return iteratorToReturn;
	}

	@Override
	public void add(E e) {
		Node<E> nodeToInsert = new Node<E>(e);
		addNodes(null, nodeToInsert, nodeToInsert, 1);
	}

	@Override
	public void add(int index, E e) {
		checkIndexRangeAdding(index);
		Node<E> nodeToInsert = new Node(e);
		Node<E> nodeBeforeToPlaceNew = getNodeBeforeToInsertNew(index);
		addNodes(nodeBeforeToPlaceNew, nodeToInsert, nodeToInsert, 1);
	}

	@Override
	public void addAll(E[] c) {
		for (E element : c) {
			add(element);
		}

	}

	@Override
	public void addAll(int index, E[] c) {
		checkIndexRangeAdding(index);
		if (c.length > 0) {
			Node<E> nodesToInsert = new Node<E>(c[0]);
			Node<E> lastNodeToInsert = nodesToInsert;
			for (int i = 1; i < c.length; i++) {
				Node<E> newLastNode
					= new Node<E>(c[i]);
				newLastNode.previous = lastNodeToInsert;
				lastNodeToInsert.next = newLastNode;
				lastNodeToInsert = newLastNode;
			}
			Node<E> nodeBeforeToPlaceNew = getNodeBeforeToInsertNew(index);
			addNodes(nodeBeforeToPlaceNew, nodesToInsert, lastNodeToInsert, c.length);
		}

	}

	@Override
	public E get(int index) {
		checkIndexRangeRetreving(index);
		Node<E> nodeOfElementToReturn = head;
		for (int i = 1; i <= index; i++) {
			nodeOfElementToReturn = nodeOfElementToReturn.next;
		}
		return nodeOfElementToReturn.element;
	}

	@Override
	public E remove(int index) {
		checkIndexRangeRetreving(index);
		Node<E> nodeToRemove = head;
		for (int i = 0; i < index; i++) {
			nodeToRemove = nodeToRemove.next;
		}
		removeNode(nodeToRemove);
		return nodeToRemove.element;
	}

	@Override
	public void clear() {
		head = null;
		tail = null;
		size = 0;
	}

	@Override
	public boolean isEmpty() {
		return (head == null);
	}

	@Override
	public void set(int index, E e) {
		checkIndexRangeRetreving(index);
		Node<E> nodeToSetNewElement = head;
		for (int i = 1; i <= index; i++) {
			nodeToSetNewElement = nodeToSetNewElement.next;
		}
		nodeToSetNewElement.element = e;
	}

	@Override
	public int indexOf(E e) {
		if (head == null) {
			return -1;
		}
		Node<E> currentNode = head;
		int index = 0;
		while (currentNode != null) {
			if (currentNode.element.equals(e)) {
				return index;
			}
			index = index + 1;
			currentNode = currentNode.next;
		}
		return -1; // seeking element hasn't been found
	}

	@Override
	public int size() {
		return size;
	}

	@Override
	public Object[] toArray() {
		Object[] arrayToReturn = new Object[size];
		if (size > 0) {
			Node<E> currentNode = head;
			for (int i = 0; i < size; i++) {
				arrayToReturn[i] = currentNode.element;
				currentNode = currentNode.next;
			}
		}
		return arrayToReturn;
	}

	@Override
	public void push(E e) {
		add(e);
	}

	@Override
	public E pop() {
		if (tail == null) {
			throw new EmptyStackException();
		}
		E elementToReturn = tail.element;
		if (tail == head) {
			tail = null;
			head = null;
		} else {
			tail.previous.next = null;
			tail = tail.previous;
		}
		size = size - 1;
		return elementToReturn;
	}

	@Override
	public void offer(E e) {
		add(e);
	}

	@Override
	public E peek() {
		return tail.element;
	}

	@Override
	public E poll() {
		if (tail != null) {
			E elementToReturn = tail.element;
			tail.previous.next = null;
			tail = tail.previous;
			size = size - 1;
			return elementToReturn;
		} else {
			return null;
		}

	}

	private void removeNode(Node<?> nodeToRemove) {
		Node<E> nodeToRemoveE = (Node<E>) nodeToRemove;
		if (nodeToRemoveE == head && nodeToRemoveE == tail) {
			head = null;
			tail = null;
		} else if (nodeToRemoveE == head) {
			nodeToRemoveE.next.previous = null;
			head = nodeToRemoveE.next;
		} else if (nodeToRemoveE == tail) {
			nodeToRemoveE.previous.next = null;
			tail = nodeToRemoveE.previous;
		} else {
			nodeToRemoveE.previous.next = nodeToRemoveE.next;
			nodeToRemoveE.next.previous = nodeToRemoveE.previous;
		}
		size = size - 1;
	}

	private void addNodes(Node<E> nodeBeforeToPlaceNew,
		Node<E> nodesToInsert, Node<E> lastNodeToInsert, int length) {
		if (nodeBeforeToPlaceNew == null) {
			if (head == null) { // insert nodes to empty list
				head = nodesToInsert;
				tail = lastNodeToInsert;
			} else { // insert nodes to tail
				tail.next = nodesToInsert;
				nodesToInsert.previous = tail;
				tail = lastNodeToInsert;
			}
		} else {
			if (nodeBeforeToPlaceNew == head) {
				head = nodesToInsert;
			} else {
				nodeBeforeToPlaceNew.previous.next = nodesToInsert;
			}
			nodeBeforeToPlaceNew.previous = lastNodeToInsert;
			lastNodeToInsert.next = nodeBeforeToPlaceNew;
		}
		size = size + length;
	}

	private void checkIndexRangeRetreving(int index) {
		if (index < 0 || index >= size) {
			throw new MyIndexOutOfBoundsException();
		}
	}

	private void checkIndexRangeAdding(int index) {
		if (index < 0 || index > size) {
			throw new MyIndexOutOfBoundsException();
		}
	}

	private Node<E> getNodeBeforeToInsertNew(int index) {
		Node<E> nodeBeforeToInsertNew = head;
		for (int i = 0; i < index; i++) {
			nodeBeforeToInsertNew = nodeBeforeToInsertNew.next;
		}
		return nodeBeforeToInsertNew;
	}

	private class MyIterator implements Iterator<E> {

		private Node<E> current;
		private Node<E> next;

		public MyIterator(Node<E> firstNode) {
			next = firstNode;
		}

		@Override
		public boolean hasNext() {
			return (next != null);
		}

		@Override
		public E next() {
			current = next;
			next = next.next;
			return current.element;
		}

		@Override
		public void remove() {
			removeNode(current);
			current = null;
		}

	}

	private class MyDescendingIterator implements Iterator<E> {

		private Node<E> current;
		private Node<E> previous;

		public MyDescendingIterator(Node<E> lastNode) {
			previous = lastNode;
		}

		@Override
		public boolean hasNext() {
			return (previous != null);
		}

		@Override
		public E next() {
			current = previous;
			previous = previous.previous;
			return current.element;
		}

		@Override
		public void remove() {
			removeNode(current);
			current = null;
		}

	}

	private static class Node<T> {

		T element;
		Node<T> previous = null;
		Node<T> next = null;

		public Node(T element) {
			this.element = element;
		}

	}
}
